package com.berchen.offer;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
 * 1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
 * 2.总节点数目为n
 * 3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)
 */
public class Test13 {
    private AtomicInteger count=new AtomicInteger(0);
    public int FindPath (TreeNode root, int sum) {
        // write code here
        if(root==null){
            return 0;
        }
        List<TreeNode> nodes=new ArrayList<>();
        getAllNode(root,nodes);

        // 将所有节点作为顶点 遍历 路径=sum的路径
        for(TreeNode node:nodes){

            equals(node,0,sum);
        }
        return count.get();
    }

    /**
     * 递归遍历 求路径之和等于sum的次数
     * @param node
     * @param he
     * @param sum
     */
    void equals(TreeNode node,Integer he,int sum){

        if(node==null){
            return;
        }
        he+=node.val;
        if(he==sum){
            count.getAndAdd(1);
//            return;   // 如果都是正数 这个return可以打开 提高效率
        }
        equals(node.left,he,sum);
        equals(node.right,he,sum);

    }

    /**
     * 获取所有节点
     * @param root
     * @param nodes
     */
    public void getAllNode(TreeNode root, List<TreeNode> nodes){

        if(root.left!=null) {
            getAllNode(root.left, nodes);
        }
        nodes.add(root);
        if(root.right!=null){
            getAllNode(root.right,nodes);
        }

    }
}
